package 力扣._128_最长连续序列;

import java.util.HashSet;
import java.util.Set;

public class Solution2 {
    public int longestConsecutive(int[] nums) {
        //先排序 不行，因为要求O(n)，那就散列表
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {   //这里共遍历n次
            //找到该序列的起始元素
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {  //在for循环结束后，这里的while的内容也最多n次，
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }

    public static void main(String[] args) {

    }
}
